package com.zzg.datastructure.linkedlist;

/**
 * @Author zhengzg
 * @Date 2022-08-17
 * @Version v1.0
 */
public class CircleSingleLinkedList {

    // 创建第一个first节点
    private Boy first = null;

    // 添加小孩节点，构建形成一个环形链表
    public void addBoy(int nums){
        // 数据校验
        if (nums < 1){
            System.out.println("输入数值错误！");
            return;
        }

        // 辅助指针，帮助构建环形链表
        Boy curBoy = null;
        for (int i = 1; i <= nums; i++) {
            // 根据编号创建小孩节点
            Boy boy = new Boy(i);
            // 如果是第一个小孩
            if (i == 1){
                // first指针指向第一个节点
                first = boy;
                // 本身指向，构成圆环
                first.setNext(first);
                // 将first节点地址赋值给辅助指针curBoy
                curBoy = first;
            } else {
                // curBoy指针地址为上一个指针的地址
                curBoy.setNext(boy);
                // 指向第一个节点，构成圆环
                boy.setNext(first);
                // 将第二个以后的Boy地址赋值给curBoy，即curBoy向后移动
                curBoy = boy;
            }
        }
    }

    // 遍历当前的环形链表
    public void showBoy(){
        if (first == null){
            System.out.println("链表中没有数据~~~");
            return;
        }

        // 因为first指针不能使用，此时使用辅助指针来遍历
        Boy curBoy = first;
        while (true){
            System.out.printf("小孩的编号 %d\n",curBoy.getNo());
            // 遍历完成
            if (curBoy.getNext() == first){
                break;
            }
            // 向后移动
            curBoy = curBoy.getNext();
        }
    }

    /**
     * 根据用户的输入，计算小孩出圈的顺序
     * @param startNo   表示从第几个小孩开始
     * @param countNum  表示数几下
     * @param nums      表示小孩总数
     */
    public void countBoy(int startNo,int countNum,int nums) {
        // 先对数据进行校验
        if (first == null || startNo < 1 || startNo > nums) {
            System.out.println("输入的数据有误，请重新输入");
            return;
        }

        // 创建辅助指针，帮助小孩完成出圈
        Boy helper = first;
        // 辅助指针，事先应该指向环形链表的最后这个节点
        // 说明helper指向最后一个小孩
        while (helper.getNext() != first) {
            helper = helper.getNext();
        }

        // 小孩报数前，先让first和helper移动k-1次
        // 因为在循环报数时，本身也会报一次但节点并不会移动，所以需要减去本身的次数
        for (int i = 0; i < startNo - 1; i++) {
            // 使节点后移
            first = first.getNext();
            helper = helper.getNext();
        }

        // 当小孩报数时，让first和helper指针同时移动 m-1次，然后出圈
        // 这里是一个循环操作，知道圈中只有一个节点
        // 说明此时圈中只有一个节点
        while (helper != first) {
            // 让first和helper指针同时移动，countNum - 1次
            // 因为本身会数一次，所以在移动时会向后移动m - 1次
            for (int i = 0; i < countNum - 1; i++) {
                first = first.getNext();
                // 让helper和first指针同时向后移动
                helper = helper.getNext();
            }
            // 循环结束，出现要出圈的节点
            System.out.printf("小孩%d 出圈\n", first.getNo());

            // 使first指针指向出圈节点的下一个节点，同时helper指针指向first节点
            first = first.getNext();
            helper.setNext(first);

        }
        // 循环结束，最后一个小孩出圈
        System.out.printf("最后留在圈中的小孩编号%d\n", first.getNo());
    }
}
